{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 随机数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 简介"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "随机数在计算机领域，尤其在密码学领域，有非常重要的应用。\n",
    "\n",
    "随机是自然界中很常见但又并不容易理解清楚的概念。比如抛一个硬币，正面或者背面向上的概率理论上各是 1/2。这个貌似是随机的，但是如果我们可以精确观测到抛出的初速度、角度、空气阻力等所有初始化条件，在宏观低速物体上(不讨论量子物理)，是可以提前计算出最后落地的正面还是背面，那这个还算随机吗？如果我做一个非常精妙的机器和实验环境，确保每次的抛出的时候的变量都精确，理论上一定可以保证每次都抛出正面。在物理界中，甚至对有没有真随机，都还是争议，但在数学里，还是给“真”随机数下了一个定义："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 定义"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "比如对于符合 0 1 二项分布的数列这样定义，假设有一个无穷数列，假设你拥有无穷时间和无穷算力，也无法通过研究前 n 项的分布规律，使得你预测 n+1 项的概率大于或小于 1/2。\n",
    "\n",
    "用极限表述就是假设有一个抛硬币游戏，对任意小的$\\epsilon$，存在一个$\\Delta$，当你研究数列大于等于 $\\Delta$次之后，你猜中的次数除以游戏总次数的比值 $\\pm 0.5$，总会小于 $\\epsilon$。\n",
    "\n",
    "这里强调一下，大于或小于 1/2, 如果下次猜对的次数小于 1/2，表示猜错的概率大于 1/2，这也不是真随机。\n",
    "\n",
    "\n",
    "这个定义在工程上其实没有可用性，我们既没有无穷的时间，也没有无穷的算力。所以我们产生随机数，特别是用软件产生的随机数，只能尽量去接近这个标准，而无法达到这一标准。事实上，\n",
    "目前没有数学证明表示密码学安全的伪随机数生成器是确实存在的。其存在性证明涉及到[$P=NP$](https://zh.wikipedia.org/wiki/P/NP%E9%97%AE%E9%A2%98)的数学难题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 计算机测试"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "随机的测试用例并不好写，因为这个问题定义就很难。我们一般的测试方式是通过大量的统计实验，计算均值和方差。概率论的知识这里暂不展开。有个终极测试方式叫[柯尔莫哥罗夫-斯米尔诺夫检验](https://zh.wikipedia.org/wiki/%E6%9F%AF%E5%B0%94%E8%8E%AB%E5%93%A5%E6%B4%9B%E5%A4%AB-%E6%96%AF%E7%B1%B3%E5%B0%94%E8%AF%BA%E5%A4%AB%E6%A3%80%E9%AA%8C) 简称 KS 测试，有兴趣的可以了解。\n",
    "\n",
    "有意思的逻辑是，一个随机算法，如果 100% 通过了随机测试，那说明它的结果是可以预测的，就不是随机算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 计算机实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "首先我们要了解一个事实，现在的所有计算机架构，是无法产生真随机数的。未来基于量子原理的量子计算机可以产生符合量子物理定义的“真随机”，但目前离实用还非常遥远。\n",
    "\n",
    "计算机的输入和输出一定是确定的。JS 里能让程序执行结果每次不确定的，无外乎 Math.random、系统时间(Date.now, performance.now 等)、硬件输入(鼠标坐标等)、I/O (接口返回，数据读取)。而其余这些都是外设，不是计算机本身。\n",
    "\n",
    "最早冯诺依曼用了一个现在看上去粗糙甚至错误的方式生成随机数:平方取中法。比如以 1234 做种子(seed)，算一下它的平方是 1522756，在左边填充 1 个 0，变成 01522756，然后他把中间四个数字输出作为随机数，就是 5227，然后再对 5227 做平方，以此类推...\n",
    "\n",
    "由于代码写出来一定是无法数学意义保密的，我们通过老冯的递推公式，和前 N 项的值，只要倒推出 seed = 1234，那我们就可以预测未来任一项的“随机数”了。\n",
    "\n",
    "然而事实上是，老冯的方法至今仍在使用，我们一直还在使用老冯的思路。所以随机数生成的安全，完全依赖于攻击者能不能在有限步下通过前 N 项找到 seed。\n",
    "\n",
    "这回到了一个很吊诡的问题：我们要写一个随机函数，首先要有一个随机的 seed，它不能硬编码在代码里，也不能有规律可循。\n",
    "\n",
    "在一般不严格的场景，我们可以使用当前系统时间做为 seed，但这在分布式系统里是不安全的，比如双 11 ，很多人都在抢 0 点，根据[抽屉原理](https://zh.wikipedia.org/zh-cn/%E9%B4%BF%E5%B7%A2%E5%8E%9F%E7%90%86)毫秒级碰撞的可能性 100%。更严格的场景，我们需要使用物理世界的一些熵来做种子，比如用户的鼠标轨迹、电流的扰动、原子的衰变等。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## JS 实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```javascript\n",
    "const random = () => {\n",
    "  return seed\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "是的，你没看错，最简单的随机函数就是直接返回 seed，只要保证每次从物理世界拿到的 seed 都是随机的，那 random 就是随机的。计算机里使用的伪随机，归根到底，不过是出于性能优化，并使工程应用上让随机数分区满足一定规则，比如区间，以及概率分布(如正态分布、泊松分布）。\n",
    "\n",
    "目前工程上使用的 random 函数，多使用[线性同余(LCG)算法](https://zh.wikipedia.org/zh-cn/%E7%BA%BF%E6%80%A7%E5%90%8C%E4%BD%99%E6%96%B9%E7%A8%8B)，这是一个简单高效的生成伪随机数方法。\n",
    "\n",
    "$x_{n+1} = \\left(ax_{n} + c\\right) \\bmod m$\n",
    "\n",
    "比如设 a = 2, c = 9，m = 11 ，种子我们选择 1，那么依次生成的随机数是如下这个数列\n",
    "\n",
    "$\\left\\langle 0, 9, 5, 8, 3, 4, 6, 10, 7, 1, \\cdots \\right\\rangle$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```javascript\n",
    "const random = (x) => {\n",
    "  const a = 2\n",
    "  const c = 9\n",
    "  const m = 11\n",
    "  return (a * x + c) % m\n",
    "}\n",
    "\n",
    "const seed = 1\n",
    "let arr = []\n",
    "\n",
    "for (let i = 0 ; i < 10; i++){\n",
    "  arr.push(random(arr.length === 0 ? seed : arr[arr.length -1]))\n",
    "}\n",
    "console.log(arr)\n",
    "// [0,9,5,8,3,4,6,10,7,1]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "你可以运行这段代码，然后你会发现再继续下去，会呈现出周期性。对于伪随机算法，使周期尽可能大是必须要具备基础条件。对于 a, c, m 这三个魔术数字，取数有一定[讲究](https://www.zhihu.com/question/22818104/answer/22744803) 。IBM 就曾经因为在自己的算法中魔术数字选取不佳，使得在统计学上失败，并使 70-90年代很多使用这个算法的科研结果被认为不可靠。足见写一个好的随机算法之难。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面这个 JS 写得不够优雅，可以使用闭包或 generator 改造，但不是本文重点。Python 里，提供了自定义 seed 的功能，这个在做一些训练调参的时候很有用，能使得多次执行结果一致。JS 没有开放指定 seed 功能，想在年会抽奖代码里用[真随机种子](https://zh.wikipedia.org/zh-cn/%E9%B4%BF%E5%B7%A2%E5%8E%9F%E7%90%86)装个 13，还得用 Python。另外 JS 的 random 返回 $(0-1)$ 区间的数，你可以对大于 1 的数求倒数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 安全"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "LCG 算法并不安全，只是高效，密码学上的安全性算法，需要更高级的数学理论，比如基于[梅森素数](https://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0)的[梅森旋转算法](https://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E6%97%8B%E8%BD%AC%E7%AE%97%E6%B3%95)。这一块我也不懂，不敢乱讲。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "数学家要做的事，就是要找到一个通项公式，公式完全对你公开，但要推出 seed，需要难度超出攻击的成本。使得一个安全问题等价于一个数学难题，难到可以拿菲尔兹奖的难度，或者暴力破解超过宇宙热寂的时间复杂度，或者存储空间超过宇宙总粒子的空间复杂度。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
